SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Benson's algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Benson's algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Benson's_algorithm_(Go)" title="Benson's algorithm (Go)">Benson's algorithm (Go)</a>, a method to find the unconditionally alive stones in the game <a href="Go_(game)" title="Go (game)">Go</a>.</div>

<p><b>Benson's algorithm</b>, named after <a href="Harold_Benson" title="Harold Benson">Harold Benson</a>, is a method for solving <a href="Multi-objective_linear_programming" title="Multi-objective linear programming">multi-objective linear programming</a> problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set".<sup id="cite_ref-Benson_1-0" class="reference"><a href="#cite_note-Benson-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The primary concept in Benson's algorithm is to evaluate the upper image of the <a href="Vector_optimization" title="Vector optimization">vector optimization</a> problem by <a href="Cutting-plane_method" title="Cutting-plane method">cutting planes</a>.<sup id="cite_ref-Lohne_2-0" class="reference"><a href="#cite_note-Lohne-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Idea_of_algorithm">Idea of algorithm</h2></div>

<p>Consider a vector linear program

</p>

</mrow>

</munder>

<mtext> subject to </mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}</annotation>

</semantics>

</math></span><img src="./93d96699cf8198dd7d61bd62d20e56443a96d7e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:26.143ex; height:3.843ex;" alt="{\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}" loading="lazy"></span></dd></dl>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\in \mathbb {R} ^{q\times n}}</annotation>

</semantics>

</math></span><img src="./bb29de3feba989f5163184d97af38fc456e2feb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.517ex; height:2.343ex;" alt="{\displaystyle P\in \mathbb {R} ^{q\times n}}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{m\times n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{m\times n}}</annotation>

</semantics>

</math></span><img src="./8025ab71ecd74b01e89f6918676203ad16cdc4a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{m\times n}}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./9fe71914e3d9fef4bce68f7b60693cc94feffde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.191ex; height:2.343ex;" alt="{\displaystyle b\in \mathbb {R} ^{m}}" loading="lazy"></span> and a polyhedral convex ordering cone <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> having nonempty interior and containing no lines. The feasible set is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}</annotation>

</semantics>

</math></span><img src="./9a9c021b658e0fc58c5ed7627ae3575f7dbfe4b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.741ex; height:2.843ex;" alt="{\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}" loading="lazy"></span>. In particular, Benson's algorithm finds the <a href="Extreme_point" title="Extreme point">extreme points</a> of the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P[S]+C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P[S]+C}</annotation>

</semantics>

</math></span><img src="./3fb09242800072c75b595baca7b41774b26ccf92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.145ex; height:2.843ex;" alt="{\displaystyle P[S]+C}" loading="lazy"></span>, which is called upper image.<sup id="cite_ref-Lohne_2-1" class="reference"><a href="#cite_note-Lohne-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>In case of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}">

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}</annotation>

</semantics>

</math></span><img src="./7b89173b74fb9e3d89d17dd00d7bb0713558f20a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:40.745ex; height:3.176ex;" alt="{\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}" loading="lazy"></span>, one obtains the special case of a multi-objective linear program (<a href="Multiobjective_optimization" class="mw-redirect" title="Multiobjective optimization">multiobjective optimization</a>).

</p>

<div class="mw-heading mw-heading2"><h2 id="Dual_algorithm">Dual algorithm</h2></div>

<p>There is a dual variant of Benson's algorithm,<sup id="cite_ref-EhrgottLöhne2011_3-0" class="reference"><a href="#cite_note-EhrgottLöhne2011-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> which is based on geometric duality<sup id="cite_ref-HeydeLöhne2008_4-0" class="reference"><a href="#cite_note-HeydeLöhne2008-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> for multi-objective linear programs.

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<p>Bensolve - a free VLP solver

</p>

<ul><li><a rel="nofollow" class="external text" href="http://bensolve.org">www.bensolve.org</a></li></ul>

<p>Inner

</p>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/lcsirmaz/inner">Link to github</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHarold_P._Benson1998" class="citation journal cs1">Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". <i>Journal of Global Optimization</i>. <b>13</b> (1): <span class="nowrap">1–</span>24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1008215702611">10.1023/A:1008215702611</a>.</cite></span>

</li>

<li id="cite_note-Lohne-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Lohne_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Lohne_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFAndreas_Löhne2011" class="citation book cs1">Andreas Löhne (2011). <i>Vector Optimization with Infimum and Supremum</i>. Springer. pp. <span class="nowrap">162–</span>169. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783642183508</bdi>.</cite></span>

</li>

<li id="cite_note-EhrgottLöhne2011-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-EhrgottLöhne2011_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFEhrgottLöhneShao2011" class="citation journal cs1">Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". <i>Journal of Global Optimization</i>. <b>52</b> (4): <span class="nowrap">757–</span>778. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10898-011-9709-y">10.1007/s10898-011-9709-y</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0925-5001">0925-5001</a>.</cite></span>

</li>

<li id="cite_note-HeydeLöhne2008-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-HeydeLöhne2008_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFHeydeLöhne2008" class="citation journal cs1">Heyde, Frank; Löhne, Andreas (2008). <a rel="nofollow" class="external text" href="http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/06-15report.pdf">"Geometric Duality in Multiple Objective Linear Programming"</a> <span class="cs1-format">(PDF)</span>. <i>SIAM Journal on Optimization</i>. <b>19</b> (2): <span class="nowrap">836–</span>845. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F060674831">10.1137/060674831</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1052-6234">1052-6234</a>.</cite></span>

</li>

</ol></div></div>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2019-01-31" href="https://en.wikipedia.org/wiki/?title=Benson's_algorithm&oldid=881154281">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>